package leetcode_day._2022._202209._2130;

/**
 * 面试题 17.19. 消失的两个数字
 * 算法：数学
 * 可以先求出 1 ~ n 的所有和 sum
 * 用 sum 减去数组中的数, 就是缺失的两数之和, x + y = sum
 * 因为数字是不重复的, 所以 x 和 y 一定在 t = ⌊sum / 2⌋ 的两边
 * 所以一定有 x <= t && y > t 存在
 * 求出 1 ~ t 所有数字之和 cur, 使用 cur 减去 nums 中所有 <= t 的 num, 就能得到 x
 * y = sum - x
 *
 * @author yzh
 * @version 1.0
 * @date 2022/9/26 20:29
 */
public class _26_面试1719 {

    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2, sum = (1 + n) * n / 2;
        for (int num : nums) sum -= num;
        int t = sum / 2, cur = (1 + t) * t / 2;
        for (int num : nums) if (num <= t) cur -= num;
        return new int[]{cur, sum - cur};
    }

}
